#define _CRT_SECURE_NO_WARNINGS
#include<stdbool.h>
#include <cstddef>

  //Definition for a binary tree node.
  struct TreeNode {
      int val;
      struct TreeNode *left;
      struct TreeNode *right;
  };



bool isUnivalTree(struct TreeNode* root)
{

    if (root == NULL)
    {
        return true;
    }
    if (root->left && root->val != root->left->val)
    {
        return false;
    }
    if (root->right && root->val != root->right->val)
    {
        return false;
    }
    return isUnivalTree(root->left) && isUnivalTree(root->right);

}
int maxDepth(struct TreeNode* root)
{
    if (root == NULL)
    {
        return 0;
    }
    int MAXRight = maxDepth(root->right);
    int MAXLeft = maxDepth(root->left);

    return (MAXLeft > MAXRight ? MAXLeft : MAXRight) + 1;

}
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
    if (p == NULL && q == NULL)
    {
        return true;
    }
    if (p == NULL || q == NULL)
    {
        return false;
    }
    if (p->val != q->val)
    {
        return false;
    }
    return isSameTree(p->right, q->right)
        && isSameTree(p->left, q->left);

}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
    if (root == NULL)
    {
        return false;
    }
    if (root->val == subRoot->val)
    {
        if (isSameTree(root, subRoot))
        {
            return true;
        }
    }
    return isSubtree(root->right, subRoot)
        || isSubtree(root->left, subRoot);


}
void PostOrder(struct TreeNode* root, int* res, int* returnSize)
{

    if (root == NULL)
    {
        return;
    }
    PostOrder(root->left, res, returnSize);
    PostOrder(root->right, res, returnSize);
    res[(*returnSize)++] = root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize)
{
    int* res = (int*)malloc(sizeof(int) * 110);
    *returnSize = 0;
    PostOrder(root, res, returnSize);
    return res;
}
void InOrder(struct TreeNode* root, int* res, int* returnSize)
{

    if (root == NULL)
    {
        return;
    }
    InOrder(root->left, res, returnSize);
    res[(*returnSize)++] = root->val;
    InOrder(root->right, res, returnSize);

}
int* inorderTraversal(struct TreeNode* root, int* returnSize)
{
    int* res = (int*)malloc(sizeof(int) * 110);
    *returnSize = 0;
    InOrder(root, res, returnSize);
    return res;
}
void preOrder(struct TreeNode* root, int* res, int* returnSize)
{
    if (root == NULL)
    {
        return;
    }
    res[(*returnSize)++] = root->val;
    preOrder(root->left, res, returnSize);
    preOrder(root->right, res, returnSize);

}
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
    int* res = (int*)malloc(sizeof(int) * 110);
    *returnSize = 0;
    preOrder(root, res, returnSize);
    return res;
}